/* 
* 实现堆数据结构。这里实现最小堆，最大堆的原理类似
*
 */
#include<stdio.h>
#include<stdlib.h>
#include<math.h>

typedef struct
{
    int max; //总容量
    int cap; //已用容量
    int *arr; //存储堆的数组
}Heap;

Heap * InitHeap(int nums);
int Insert(Heap *heap, int val);
void Pop(Heap *heap, int *res);
void ShiftUp(int *arr, int index);
void ShiftDown(int *arr, int length, int index);
/* 
 * 初始化堆
 * @param int  元素数量
 * @return  Heap*
 */
Heap * InitHeap(int nums){
    if(nums<1){
        printf("nums must greater then 0");
        exit(-1);
    }   
    Heap *heap;
    heap = (Heap*)malloc(sizeof(Heap));
    if(heap==NULL){
        printf("Init heap fail");
        exit(-1);
    }
    heap->max = nums;
    heap->cap = 0;
    heap->arr = (int*)malloc(nums*sizeof(int));

    if(heap->arr==NULL){
        printf("Init heap fail");
        exit(-1);
    }

    return heap;
}

/** 
 * 插入元素，成功返回0，失败返回-1
 * 
 */
int Insert(Heap *heap, int val){
    // 满了
    if(heap->max==heap->cap){
        return -1;
    }
    // 放入数组末尾
    heap->arr[heap->cap] = val;
    // 节点上移
    ShiftUp(heap->arr, heap->cap);
    heap->cap++;

    return 0;
}

/** 
 * 取堆顶元素
 * 
 */
void Pop(Heap *heap, int *res){
    if(heap->cap==0){
        res = NULL;
        return;
    }

    *res = heap->arr[0];
    // 最后一个元素放到堆顶
    heap->arr[0] = heap->arr[heap->cap-1];
    heap->cap--;
    // 根结点向下调整堆
    ShiftDown(heap->arr, heap->cap, 0);
    
    return;
}

/** 
 * 向上调整元素的位置，使其符合堆的性质 
 * @param  array 保存堆的数组
 * @param  int 结点在数组中的下标
 */
void ShiftUp(int *arr, int index){
    if(arr == NULL || index < 1){
        return;
    }
    int parentIndex,parent;
    parentIndex = index >> 1;
    parent = arr[parentIndex];
    while (index !=0 && parent > arr[index])
    {
        // 父节点和子节点交换位置
        arr[parentIndex] = arr[index];
        arr[index] = parent;
        index = parentIndex;
        parentIndex = index >>1;
        parent = arr[parentIndex];
    }
    return;
}

/** 
 * 向下调整元素的位置，使其符合堆的性质 
 * @param  array 保存堆的数组
 * @param  int 数组的长度
 * @param  int 结点在堆数组中的下标
 */
void ShiftDown(int *arr, int length, int index){ 
    int childIndex,tmp;
    int *child = NULL;
    // 没有子节点直接返回
    if(2*index+1 > length)
        return;
    //第一个子节点存在
    childIndex = 2*index+1;//第一个子节点的索引
    child = arr+childIndex;
     
    if( (2*index+2 < length) && (*child > arr[2*index+2]) ){
        //第二个子节点存在且第二个子节点的值小于第一个子节点，取第二个子节点和父节点交换
        childIndex = 2*index+2; // 第二个子节点的索引
        child = arr+childIndex;
    }

    // 存在子节点且子节点的值小于父节点
    while(child != NULL  &&  *child < arr[index]){
        // 交换
        tmp = arr[childIndex];
        arr[childIndex] = arr[index];
        arr[index] = tmp;

        child = NULL;
        index = childIndex;
        if(2*index+1 > length)
            return;
        
        childIndex = 2*index+1;//第一个子节点的索引
        child = arr+childIndex;
        
        
        if( (2*index+2 < length) && (*child > arr[2*index+2]) ){
            childIndex = 2*index+2; // 第二个子节点的索引
            child = arr+childIndex;
        }
    }

}

// 打印存储数组
void PrintHeap(Heap *heap){
    printf("\n**********************Heap,cap:%d,avl:%d**************************\n",
     heap->cap, heap->max-heap->cap);
    for(int i=0; i<heap->cap; i++){
        printf("%d\t", heap->arr[i]);
    }
    printf("\n");
}


/* 堆排序 */
void  HeapSort(int *arr, int n){
    if( arr== NULL || n < 2)
        return;
    int i;
    int tmp;
    // 构造最小堆
    for ( i = 1; i < n; i++)
    {
        // 向上调整结点位置，构造最小堆
        ShiftUp(arr, i);
    }

    for ( i = n-1; i > 0; i--)
    {
        // 交换堆顶元素和最后一个元素
        tmp =  arr[0];
        arr[0] = arr[i];
        arr[i] = tmp;
        // 交换之后向下调整结点位置
        ShiftDown(arr, i, 0);
        
    }
    
    return;
}


// int main()
// {
//     int val;
//     Heap *heap;
//     // 测试数组
//     int testArr[11] = {2,3,4,1,10,7,5,6,8,9,11};
//     printf("测试数组\n:");
//     for(int i=0; i<11; i++){
//         printf("%d\t", testArr[i]);
//     }
//     printf("\n");
//     heap = InitHeap(15);
//     for(int i=0; i<11; i++){
//         Insert(heap, testArr[i]);
//     }
//     PrintHeap(heap);
//     for(int i=0; i<11; i++){
//         Pop(heap, &val);
//         PrintHeap(heap);
//     }
// }

